1. Field of the Invention
The present invention relates to a method for effective generation and calculation of a 2-dimensional motion path applied to a computer, and more particularly, to a method in which a direction map is used to calculate a 2-dimensional convolution and to finally generate a configuration-space obstacle (or c-space obstacle) so as to solve a problem caused in generating a 2-dimensional motion path that requests to move on 2-dimension without collision between obstacles.
2. Description of the Related Art
Generally, a c-space obstacle is a mathematical curve that is defined using convolution (represented by *) or Minkowski addition (represented by ⊕) and Minkowski subtraction (represented by ⊖) operations on basis of calculation geometry.
For example, the c-space obstacle for the obstacle A and the object B is defined as a curve ∂P such as the following Equation 1.TRIM(∂A*∂(−B))=∂(A ⊕(−B)=∂Pout  [Equation 1]
Well known is mathematically a fact that if the object B moves along a path ∂Pout according to the Equation 1, a collision with the obstacle A is not generated. In the Equation 1, the −B means that the object is rotated by 180 degree with respect to the origin.
However, in the above Equation, the convolution, the TRIM, and Minkowski addition are very complex operations and has rather much calculation amount. Furthermore, when the size of the obstacle or the object is variable, the path ∂Pout should be calculated in every case.
Further, the calculation method is different depending on whether a motion range of the object belongs to an internal or external of the obstacle. For example, the Equation 1 is a method for calculating the path of the object at the external of the obstacle, but Minkowski subtraction operation should be used as in Equation 2 so as to calculate the path at the internal of the obstacle. In the Equation 2, when the object B moves along the ∂pout at the internal of the obstacle A, a collision with a boundary of the A is not generated.TRIM((∂At*∂(−B))t)=∂(A⊖(−B))=∂Pε  [Equation 2]
However, a practical method is almost not known until now in which the above one paired Minkowski addition and subtraction are simultaneously calculated using the convolution operation or other ways.